
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

typedef int keytype;

void binary_insert(vector<keytype> &keys)
{
  int low, high, mid;
  int i, j;
  keytype k;

  for (i = 1; i < keys.size(); i++){
    low = 0; high = i - 1;
    while (low <= high){
      mid = (low + high) / 2;
      if (keys[i] > keys[mid])
	low = mid + 1;
      else
	high = mid - 1;
    }
    k = keys[i];
    for (j = i - 1; j >= low; j--)
      keys[j+1] = keys[j];
    keys[low] = k;
  }
}

void print(vector<keytype> &keys)
{
  for (auto it = keys.begin(); it != keys.end(); it++)
    cout << *it << "\t";
  cout << endl;
}

int main()
{
  ifstream in("sort.txt");
  vector<keytype> keys;
  keytype k;

  assert(in);
  while (in >> k)
    keys.push_back(k);

  binary_insert(keys);
  print(keys);
  in.close();

  return 0;
}


